package com.zz.node;

public class LCR171Solution {
    /**
     * 真是令人破防的解法
     * headA的长度为a，headB的长度为b，公共节点的长度为c
     * 如果 a + (b - c) = b + (a - c)
     * 那么返回当时相等的那个节点，否则就null
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 差值法
        int len1 = 0, len2 = 0;
        ListNode node1 = headA;
        ListNode node2 = headB;
        while (node1 != null) {
            node1 = node1.next;
            len1++;
        }
        while (node2 != null) {
            node2 = node2.next;
            len2++;
        }

        node1 = headA;
        node2 = headB;
        int diff = Math.abs(len1 - len2);
        if(len1 > len2) {
            node1 = diffValue(node1, diff);
        }else{
            node2 = diffValue(node2, diff);
        }

        // 到此两个链表的长度已经相同
        while (node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }

    /**
     * 令一个节点移动 n 步
     * @param node 那条链表
     * @param diff 移动步数
     * @return
     */
    public ListNode diffValue(ListNode node, int diff){
        while(diff > 0){
            diff--;
            node = node.next;
        }
        return node;
    }
}
